/**
 * 版权所有 2009-2012山东新北洋信息技术股份有限公司
 * 保留所有权利。
 */
package com.linyaonan.leetcode.medium._54;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 给定一个包含 m x n 个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。
 *
 * 示例 1:
 *
 * 输入:
 * [
 *  [ 1, 2, 3 ],
 *  [ 4, 5, 6 ],
 *  [ 7, 8, 9 ]
 * ]
 * 输出: [1,2,3,6,9,8,7,4,5]
 * 示例 2:
 *
 * 输入:
 * [
 *   [1, 2, 3, 4],
 *   [5, 6, 7, 8],
 *   [9,10,11,12]
 * ]
 * 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
 *
 *
 * @ProjectName: leetcode
 * @Package: com.linyaonan.leetcode.medium._54
 * @ClassName: SpiralMatrix
 * @Author: linyaonan
 * @Date: 2020/1/21 17:22
 */
public class SpiralMatrix {

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        if (matrix.length == 0 || matrix[0].length == 0) {
            return result;
        }
        // 指定起始四个坐标
        int startX = 0;
        int endX = matrix[0].length - 1;
        int startY = 0;
        int endY = matrix.length - 1;

        // 结束条件为不能继续循环
        while(startX <= endX && startY <= endY) {
            // 1. 横向向右
            for (int i = startX; i <= endX; i++) {
                result.add(matrix[startY][i]);
            }
            // Y向下走
            startY++;
            // 2. 纵向向下
            if (startY > endY) {
                break;
            }
            for (int i = startY; i <= endY; i++) {
                result.add(matrix[i][endX]);
            }
            // X向内走
            endX--;
            if (startX > endX) {
                break;
            }
            // 3. 横向向左
            for (int i = endX; i >= startX; i--) {
                result.add(matrix[endY][i]);
            }
            // Y向上走
            endY--;
            if (startY > endY) {
                break;
            }
            // 4. 纵向向上
            for (int i = endY; i >= startY; i--) {
                result.add(matrix[i][startX]);
            }
            startX++;
        }

        return result;
    }

    /**
     * 打印螺旋矩阵
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder2(int[][] matrix) {
        // 特殊边界
        if (matrix.length == 0 || matrix[0].length == 0) {
            return new ArrayList<>();
        }
        // 定义每次遍历的起始位置与终止位置
        int startX = 0;
        int endX = matrix.length - 1;
        int startY = 0;
        int endY = matrix[0].length - 1;
        int length = matrix.length * matrix[0].length;
        List<Integer> result = new ArrayList<>(length);
        int count = 0;
        while(startX <= endX && startY <= endY) {
            // 1. 从左向右横向
            for (int i = startY; i <= endY && count < length; i++) {
                result.add(matrix[startX][i]);
                count++;
            }
            // 2. 右侧竖向向下
            startX++;
            for (int i = startX; i <= endX && count < length; i++) {
                result.add(matrix[i][endY]);
                count++;
            }
            // 3. 从右向左横向
            endY--;
            for (int y = endY; y >= startY && count < length; y--) {
                result.add(matrix[endX][y]);
                count++;
            }
            endX--;
            // 4. 左侧竖向向上
            for (int x = endX; x >= startX && count < length; x--) {
                result.add(matrix[x][startY]);
                count++;
            }
            startY++;
        }

        return result;
    }
}
